package chart.树的遍历;

import chart.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author yzh
 * @data 2021/3/25 10:59
 */
public class TreeBFS {
    public static void main(String[] args) {
        TreeNode<Integer> node1 = new TreeNode<>(1);
        TreeNode<Integer> node2 = new TreeNode<>(2);
        TreeNode<Integer> node3 = new TreeNode<>(3);
        TreeNode<Integer> node4 = new TreeNode<>(4);
        node1.left = node2;
        node1.right = node4;
        node2.left = node3;
        System.out.println(bfs(node1));
    }


    /**
     * 广度优先搜索
     * 一层一层地遍历
     * 把节点放入队列中
     * Breadth first search
     * @param root
     */
    public static String bfs(TreeNode<Integer> root) {
        StringBuilder ans = new StringBuilder();
        Deque<TreeNode<Integer>> queue = new ArrayDeque<>();
        if (root != null) queue.offerLast(root);
        while (!queue.isEmpty()) {
            TreeNode<Integer> node = queue.pollFirst();
            ans.append(node.val);
            if (node.left != null) queue.offerLast(node.left);
            if (node.right != null) queue.offerLast(node.right);
        }
        return ans.toString();
    }

}
